#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <list>
using namespace std;



//为了存能存储键值对，提供了ValueType
template <class KeyType,class ValueType>
struct AVLTreeNode
{
    AVLTreeNode(const pair<KeyType,ValueType> &kv = make_pair(KeyType(),ValueType()))
    :_kv(kv),left(nullptr),right(nullptr),parent(nullptr),balancefactor(0)
    {

    }
    pair< KeyType, ValueType> _kv;
    AVLTreeNode<KeyType,ValueType> *left;
    AVLTreeNode<KeyType,ValueType> *right;
    AVLTreeNode<KeyType,ValueType> *parent;
    int balancefactor;
};

template <class KeyType,class ValueType>
class AVLTree
{
    private: typedef AVLTreeNode<KeyType,ValueType>* AVLTreeNodePtr;
    AVLTreeNodePtr m_root = nullptr;
    public:
    int height(AVLTreeNodePtr root)
    {
        if(root==nullptr)
        {
            return 0;
        }
        int leftheight = height(root->left);
        int rightheight = height(root->right);
        return 1+(leftheight>rightheight?leftheight:rightheight);
    }

    //右旋
    AVLTreeNodePtr  RightRotate(AVLTreeNodePtr root)//传要传输的旋转的父节点其父亲所指向的那个节点
    {
        AVLTreeNodePtr left = root->left;
        AVLTreeNodePtr Childright = left->right;
        
        root->left = Childright;
        if(Childright)
        {
            Childright->parent = root;
        }
        //节点之间的值就算交换完毕
        
        left->right = root;
        root->parent = left;

        return left;
    }
    //左旋
    AVLTreeNodePtr LeftRotate(AVLTreeNodePtr root)
    {
        AVLTreeNodePtr right = root->right;
        AVLTreeNodePtr Childleft = right->left;

        root->right = Childleft;
        if(Childleft)
        {
            Childleft->parent = root;
        }

        right->left = root;
        root->parent = right;

        return right;
    }
    //为了复用代码减去不必要的实现，这里实现了函数指针复用左旋右旋
    void Rotate(AVLTreeNodePtr parent,AVLTreeNodePtr(AVLTree<KeyType, ValueType>::*Rotatefunc)(AVLTreeNodePtr))
    {
        AVLTreeNodePtr PP = parent->parent;
        if(PP)
        {
            AVLTreeNodePtr Child = (this->*Rotatefunc)(parent);
            if(PP->left == parent)
            {
                PP->left = Child;
                Child->parent = PP;
            }
            else
            {
                PP->right = Child;
                Child->parent = PP;
            }
        }
        else//说明遇见了根节点
        {
            m_root= (this->*Rotatefunc)(parent);
            m_root->parent = nullptr;
        }
    }
    bool insert(const pair<KeyType,ValueType> &kv)
    {
        if(m_root==nullptr)
        {
            m_root=new AVLTreeNode(kv);
            return true;
        }
        AVLTreeNodePtr p=m_root;
        AVLTreeNodePtr parent=nullptr;
        while(p!=nullptr)
        {
            parent=p;
            if(kv.first<p->_kv.first)
            {
                p=p->left;

            }
            else if(kv.first>p->_kv.first)
            {
                p=p->right;
            }
            else//已经存在相同的值,
            {
                return false;
            }
        }
        p = new AVLTreeNode(kv);
        p->parent=parent;
        if(kv.first<parent->_kv.first)
        {
            parent->left=p;
        }
        else 
        {
            parent->right=p;
        }
        //至此节点增加完毕

        // test print
        // LevelPrint();
        while(parent)
        {
            if(p==parent->left)
            {
                parent->balancefactor--;
            }
            else
            {
                parent->balancefactor++;
            }

            if(0==parent->balancefactor)//恰好插入合适
            {
                //包含-1到0,1到0两种平衡因子转换情况。
                break;
            }
            else if(parent->balancefactor==1 || parent->balancefactor==-1)
            {
                //是这两种结果，只会是0->1或者0->-1
                //这样的话，就一定不止父节点高度改变，其祖先节点，也一定收到了影响
                //这种时候就需要依次调整节点，把每一处的该调整的都调整了
                p = parent;
                parent = p->parent;
            }
            else
            {
                //倘若是这两种结果，就必然是1->2和-1->-2
                //如果是这种结果就意味着，已经失去满足平衡的条件（平衡因子绝对值小于1）
                //这个时候，对当前父节点以及其子孙为单位，进行旋转调整使得其平衡


                //我们针对这种情况进行思考，
                //因为平衡要求的缘故，我们加节点两种情况，加在左子树和加在右子树
                //但是由于平衡因子的缘故，树高度会存在1的高度差，
                //及左子树更高，或者右子树更高
                //综合两种情况，我们得知
                //在左子树更高左边，加节点  -- 左左
                //右子树更高加在右边        --右右
                //以及左右，右左（搁置下，往后再讨论）
                if(2==parent->balancefactor)//因子为2，说明加在右子树,因为显然不断向上加1，最后会是2，
                {
                    if(1==p->balancefactor)
                    {
                        parent->balancefactor=p->balancefactor = 0;
                        //说明是右子树更高，且加在右子树    
                        Rotate(parent,&LeftRotate);
                        
                    }
                    else if(-1==p->balancefactor)//左子树更高，加在右子树
                    {
                        AVLTreeNodePtr tpson = p->left;
                        p->balancefactor = p->left->balancefactor = 0;
                        Rotate(p,&RightRotate);
                        Rotate(parent,&LeftRotate);
                        parent->balancefactor=GetBS(parent);
                        p->balancefactor=GetBS(p);
                        tpson->balancefactor=GetBS(tpson);
                    }
                }
                else if(-2==parent->balancefactor)
                {
                    if(-1==p->balancefactor)
                    {
                        parent->balancefactor=p->balancefactor = 0;
                        Rotate(parent,&RightRotate);
                    }
                    else if(1==p->balancefactor)
                    {
                        AVLTreeNodePtr tpson = p->right;
                        Rotate(p,&LeftRotate);
                        Rotate(parent,&RightRotate);
                        parent->balancefactor=GetBS(parent);
                        p->balancefactor=GetBS(p);
                        tpson->balancefactor=GetBS(tpson);
                    }
                }
                break;
            }
        }
        //test print
        // LevelPrint();
        // cout<<"***********************************\n";
        return 1;
    }
    //算平衡因子
    int GetBS(AVLTreeNodePtr root)
    {
        if(root==nullptr)
        {
            return 0;
        }
        return height(root->right)-height(root->left);
    }
    //中序打印
    void InorderPrint()
    {
        InorderPrintR(m_root);
        cout<<"\n";
    }
    void InorderPrintR(AVLTreeNodePtr root)
    {
        if(root==nullptr)
        {
            return ;
        }
        InorderPrintR(root->left);
        cout<<root->_kv.first<<" ,";
        InorderPrintR(root->right);
    }
    //层序遍历打印，以观察值
    vector<vector<pair<KeyType,ValueType>>> LevelPrint()
    {
        vector<vector<pair<KeyType,ValueType>>> res;
        list<AVLTreeNodePtr> nodelist(1,m_root);
        int NowNodeNum = 1,nextLevelNodeNum = 0;
        vector<pair<KeyType,ValueType>> nowlevel;
        while(nodelist.size())
        {
            AVLTreeNodePtr p = nodelist.front();
            nodelist.pop_front();
            nowlevel.push_back(p->_kv);
            if(p->left)
            {
                nodelist.push_back(p->left);
                nextLevelNodeNum++;
            }
            if(p->right)
            {
                nodelist.push_back(p->right);
                nextLevelNodeNum++;
            }

            if(--NowNodeNum==0)
            {
                res.push_back(nowlevel);
                nowlevel.clear();
                NowNodeNum = nextLevelNodeNum;
                nextLevelNodeNum = 0;
            }
        }
        for (int i = 0; i < res.size(); i++)
        {
            for (int j = 0; j < res[i].size(); j++)
            {
                cout << res[i][j].first << " ," ;
            }
            cout<<endl;
        }
        cout<<"********************************\n";
        return res;
    }

    //检验是否是一颗合格的二叉平衡树
    bool test()
    {
        list<AVLTreeNodePtr> nodelist(1,m_root);
        int NowNodeNum = 1,nextLevelNodeNum = 0;
       while(nodelist.size())
        {
            AVLTreeNodePtr p = nodelist.front();
            nodelist.pop_front();
            int NowBS = height(p->right)-height(p->left);
            if(NowBS !=p->balancefactor)
            {
                cout<<"error Tree"<<endl;
                return 0;
            }
            if(p->left)
            {
                nodelist.push_back(p->left);
                nextLevelNodeNum++;
            }
            if(p->right)
            {
                nodelist.push_back(p->right);
                nextLevelNodeNum++;
            }

            if(--NowNodeNum==0)
            {

                NowNodeNum = nextLevelNodeNum;
                nextLevelNodeNum = 0;
            }
        }
        cout<<"True tree"<<endl;
        return 1;
    }
};